package array.Binary_Search;
/*      给你一个非负整数 x ，计算并返回 x的算术平方根 。

        由于返回类型是整数，结果只保留 整数部分 ，小数部分将被舍去 。

        注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

        示例 1：
        输入：x = 4
        输出：2

        示例 2：
        输入：x = 8
        输出：2
        解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。*/
public class lc69 {
    public static void main(String[] args) {
        System.out.println(mySqrt2(2147395599));
        System.out.println(mySqrt2(808201));
        if(808201==899*899) System.out.println(true);


    }
    int s;
    public int mySqrt(int x) {
        s=x;
        if(x==0) return 0;
        return ((int)(sqrts(x)));
    }
    public double sqrts(double x){
        double res = (x + s / x) / 2;
        if (res == x) {
            return x;
        } else {
            return sqrts(res);
        }
    }
    public static int mySqrt2(int x) { //二分查找
        //可用二次不等式证明，当x>4时，根号x＜x/2
        //因此二分查找的右侧即为x/2
        //1-4的情况单独写出即可
        int low=0;
        int high=x/2;
        int mid=(low+high)/2;
        if(x==0){
            return 0;
        } else if(x>=1&&x<=3){
            return 1;
        } else if(x==4){
            return 2;
        }else {
             low=0;
             high=x/2;
            // mid=(low+high)/2;
            while(low<=high){
                mid = low + (high - low ) / 2;
                if(mid <= x / mid && (mid + 1) > x / (mid + 1)){   //写判断条件时，可使用÷代替×，避免越界
                    return mid;   //(mid < x / mid && (mid + 1) > x / (mid + 1))||mid ==x / mid
                } else if (x/mid<mid) {
                    high=mid-1;
                } else  {
                    low=mid+1;
                }
            }
            return 0;
            
        }

        
    }
   
}
